package top.dprkshow.practice.graph;

/**
 * @author Kent HAN
 * @date 2021/9/15
 */
public class SCC {
    private int count;
    private boolean[] visited;
    private int[] id;

    public SCC(Digraph g) {
        count = 0;
        visited = new boolean[g.getTotalVertices()];
        id = new int[g.getTotalVertices()];
    }

    public void init(Digraph g) {
        Digraph reversedGraph = g.reverse();
        ReversePostOrder reversePostOrder = new ReversePostOrder(reversedGraph);
        reversePostOrder.init(reversedGraph);
        for (int i : reversePostOrder.reversePost) {
            if (!visited[i]) {
                dfs(g, i);
                count++;
            }
        }
    }

    public int count() {
        return count;
    }

    public int id(int v) {
        return id[v];
    }

    private void dfs(Digraph g, int i) {
        visited[i] = true;
        id[i] = count;
        for (int adjVertex : g.adj(i)) {
            if (!visited[adjVertex]) {
                dfs(g, adjVertex);
            }
        }
    }
}
